import java.util.List;
import java.util.Scanner;
class ListNode {
    ListNode next;
    int val;

    ListNode(int val) {
        this.val = val;
    }

    //class ListNode<E>{
//    E val;
//    ListNode<E> next;
//
//    ListNode(E val){
//        this.val =val;
//    }
//
//}
    public static class Lexicographic_order {
        public static void main(String[] args) {
            ListNode head = new ListNode(1);
            ListNode nextNode;
            nextNode = head;
            //创建链表
            for (int i = 2; i <= 4; i++) {
                ListNode node = new ListNode(i);
                nextNode.next = node;
                nextNode = nextNode.next;
            }
            nextNode = head;
            print(nextNode);
            print(method(nextNode));

        }

        //打印
        static void print(ListNode listNode) {
            //创建链表的几点
            while (listNode != null) {
                System.out.println("节点：" + listNode.val);
                listNode = listNode.next;
            }
            System.out.println();
        }

        public static ListNode method(ListNode head) {
            ListNode defaultHead = head;
            int count = 1;
            //新建一个链表用于存储结果
            ListNode newHead = head;
            boolean flag = false;
            /**
             * 先构造一个环
             */
            while (head.next != null) {
                count++;
                head = head.next;
            }
            head.next = defaultHead;
            for (int i = 0; i < count; i++) {
                if (flag == true) {
                    break;
                }
                newHead = newHead.next;
                ListNode tempNode1 = newHead;
                ListNode tempNode2 = defaultHead;
                for (int j = 0; j < count; j++) {
                    if (tempNode1.val == tempNode2.val) {
                        tempNode1 = tempNode1.next;
                        tempNode2 = tempNode2.next;

                    } else if (tempNode1.val < tempNode2.val) {
                        flag = true;
                        break;
                    } else {
                        break;
                    }
                }
            }
            if (flag == false) {
                return null;
            }

            ListNode copyNewHead = newHead;
            for (int i = 0; i < count; i++) {
                copyNewHead = copyNewHead.next;
            }
            copyNewHead.next = null;
            return newHead;
        }
    }
}
